package main

import (
	"fmt"
	"sort"
)

/**
https://www.youtube.com/watch?v=mNzUMPBiRX4
https://zh.wikipedia.org/wiki/3SUM
https://www.youtube.com/watch?v=gq-uWp327m8

O(n^2)

首先对所有数字进行排序
然后指定一个基准数，从左向右依次遍历，(3个数一组，基准数是第一个数，所以其值区间为0,len(nums)-2)，
此后转化为2sum的问题，num1+ num2 = sum-base

其中需要注意的点是一组中的三个数不能出现历史重复的数字
*/
func threeSum(nums []int) [][]int {
	sort.Ints(nums)
	l := len(nums)
	res := [][]int{}
	for base := 0; base < l-2; base++ {
		if base > 0 && nums[base] == nums[base-1] {
			continue
		}

		start := base + 1
		end := l - 1
		target := 0 - nums[base]

		for start < end {
			if nums[start]+nums[end] == target {
				res = append(res, []int{nums[start], nums[end], nums[base]})
				for start < end && nums[start] == nums[start+1] {
					start++
				}
				for start < end && nums[end] == nums[end-1] {
					end--
				}

				start++
				end--

			} else if nums[start]+nums[end] < target {
				start++
			} else {
				end--
			}
		}
	}

	return res
}

func main() {
	fmt.Println(threeSum([]int{-1, 0, 1, 2, -1, -4}))
}
